[BAEKJOON] 5710. 전기 요금

문제 :

최근에 전기 회사는 전기 요금을 또 올렸다. 새로운 전기 요금은 아래 표에 나와있다. (사용량은 항상 양의 정수)

위의 표를 읽는 방법은 다음과 같다.

사용량의 첫 100Wh의 가격은 1Wh당 2원이다. 다음 9900Wh (101 ~ 10000)의 가격은 1Wh당 3원이다. 이런식으로 계속 계산한다.

예를 들어, 10123Wh를 사용했을 때, 내야하는 요금은 2×100 + 3×9900 + 5×123 = 30515원이다.

전기 회사는 전기 요금을 인상하지 않고 돈을 더 버는 이상한 방법을 만들었다. 그 방법은 바로 사용한 전기의 양을 알려주지 않고, 얼마를 내야 하는지 알려주는 것이다. 전기 회사는 요금과 관련된 정보를 나타내는 두 숫자 A와 B를 알려준다. A와 B는 전기 회사에서 그 사람이 사는 건물에서 임의로 고른 이웃의 정보와 합친 요금이다.

• A: 이웃의 사용량과 사용량을 합쳤을 때 내야하는 요금
• B: 이웃의 전기 요금과의 차이 (절댓값)

위의 두 숫자를 이용해서 자신이 얼마를 내야 하는지를 계산할 수 없을 때는, 계산 요금을 100원을 더 내면 전기 회사에서 사용량을 알려준다.

상근이는 매우 전기를 아끼는 사람이다. 따라서, 항상 자신이 사는 건물에서 가장 전기를 적게 쓴다고 확신한다. 상근이는 돈도 전기만큼 아낀다. 따라서, 절대로 계산 요금을 지불하지 않고 자신이 직접 계산할 것이다.

예를 들어, A = 1100, B = 300이라고 하자. 이 정보를 이용하면, 상근이의 사용량은 150Wh, 이웃의 사용량은 250Wh임을 알 수 있다. 두 사람의 총 사용량은 400Wh이다. 따라서, A = 2×100 + 3×300 = 1100이 된다. 따라서, 상근이는 350원을 내면 된다. 상근이의 이웃은 2×100 + 3×150 = 650원을 내야 하고, B = |350 - 650| = 300이 된다.

A와 B가 주어졌을 때, 상근이가 내야하는 전기 요금을 구하는 프로그램을 작성하시오.

입력 :

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 109) 항상 정답이 유일한 경우만 주어지며, 입력으로 주어지는 두 숫자를 만들 수 있는 사용량은 딱 한 쌍 존재한다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력 :

각 테스트 케이스에 대해서, 상근이가 내야 하는 요금을 출력한다.

풀이 :

문제는 접근 자체가 엄청 어려운 문제는 아니였으나, 주어진 조건이 두 사용자의 합친 요금과 두 사용자의 전기 요금 차이의 절대값이 주어지게되는데, 여기서 요금 차이가 아니라 사용량 차이가 주어졌다면 훨씬 쉬운 문제였겠지만 본 문제는 그 조건이 아니기 때문에 중간에 이분 탐색 과정이 들어가야 해서 조금 꼬아져 있는 문제 같았다.

[ 세부 구현사항 ]

• 우선 사용량으로 요금을 계산하는 함수 usedToCost() 와, 요금으로 사용량을 계산하는 costToUsed() 함수가 필요하다.
• 본 함수 두개를 간단하게 구현한 이후에는 이분 탐색을 활용해서 나의 사용량 및 요금을 구할 수 있어야 한다. 처음에는 이분 탐색이 아니라 총 사용량의 범위에서 반복문을 돌려 사용량을 판단했는데 본 방법의 경우 사용량이 최대 1억이 넘는 경우이기 때문에 무조건적으로 시간초과가 발생한다. 따라서 단순 반복문 탐색 형식이 아니라 이분 탐색을 통해 나의 사용량을 판단해야 한다.
• 내가 생각한 이분탐색 방식은 우선 나의 사용량이 이웃 사용량보다 무조건 작고 차이값 자체 또한 절대값으로 제공하기는 하나 (이웃 사용량) - (나의 사용량) 으로 연산할 경우 무조건 차이값이 양의 정수 값을 가지기 때문에 이러한 점을 활용했다.
• 즉, 나의 사용량은 무조건 총 사용량의 절반보다 작기 때문에 left = 1, right = totalused / 2로 정해서 이분탐색을 진행해주면 문제를 반복문 형태보다 훨씬 빠른 속도로 진행할 수 있다.

코드 :

#include <iostream>

using namespace std;

int costToUsed(int cost) {
    int amount = 0;
    int boundaries[3] = {100, 9900, 990000};
    int costs[3] = {2, 3, 5};

    for (int i = 0; i < 3; i++) {
        if (cost <= boundaries[i] * costs[i]) return amount + cost / costs[i];
        amount += boundaries[i];
        cost -= boundaries[i] * costs[i];
    }
    return amount + cost / 7;
}

int usedToCost(int used) {
    int curcost = 0;
    int boundaries[4] = {0, 100, 10000, 1000000};
    int costs[4] = {0, 2, 3, 5};

    for (int i = 1; i < 4; i++) {
        if (used <= boundaries[i]) return curcost + costs[i] * (used - boundaries[i - 1]);
        curcost += costs[i] * (boundaries[i] - boundaries[i - 1]);
    }
    return curcost + 7 * (used - 1000000);
}

int main() {
    int totalcost, totalused, costdif;
    while (true) {
        cin >> totalcost >> costdif;
        if (!totalcost && !costdif) break;
        totalused = costToUsed(totalcost);
        int left = 1, right = totalused / 2;

        while (left <= right) {
            int mid = (left + right) / 2;
            int mycost = usedToCost(mid), yourcost = usedToCost(totalused - mid);

            if (yourcost - mycost == costdif) {
                cout << mycost << '\n';
                break;
            } else if (yourcost - mycost < costdif) right = mid - 1;
            else left = mid + 1;
        }
    }
    return 0;
}